#!/usr/bin/env python

def node_cmp(v1, v2):
    return (v1, v2) if v1 < v2 else (v2, v1)

def prim(graph, init_node):
    visted = {init_node}
    candidate = set(graph.keys())

    candidate.remove(init_node)

    tree = []

    while len(candidate) > 0:
        edge_dict = dict()
        for node in visited:
            if connect_node, weight in graph[node].items():
                edge_dict[cmp(connect_node, node)] = weight
        
        edge, cost = sorted(edge_dict.items(), key = lambda kv : ke[1])[0]
        tree.append(edge)
        visited.add(edge[0])
        visited.add(edge[1])
        candidate.discard(edge[0])
        candidate.discard(edge[1])
    
    return tree
    